#define _CRT_SECURE_NO_WARNINGS

class Solution {
public:
    int waysToStep(int n) {
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;

        int MOD = 1000000007;
        vector<int> dp({ 1, 2, 4 });
        for (int i = 4; i <= n; i++)
        {
            int sum = ((dp[0] + dp[1]) % MOD + dp[2]) % MOD;
            dp[0] = dp[1];
            dp[1] = dp[2];
            dp[2] = sum;
        }

        return dp[2];
    }
};